/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-09
 * Time: 17:12
 */


   class ListNode {
     int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //链表为空时
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode newH = null;
        ListNode newCur = null;

        //从头遍历各链表 谁值小 谁就尾插到新链表中
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                if (newH == null) {
                    newH = newCur = cur1;
                }else {
                    newCur.next = cur1;
                    newCur = newCur.next;
                }
                cur1 = cur1.next;
            }else {
                if (newH == null) {
                    newH = newCur = cur2;
                }else {
                    newCur.next = cur2;
                    newCur = newCur.next;
                }
                cur2 = cur2.next;
            }
        }

        //某一链表的元素全部插入后，将另一链表剩余元素直接拼接即可
        if (cur1 == null) {
            newCur.next = cur2;
        }
        if (cur2 == null) {
            newCur.next = cur1;
        }
        return newH;
    }
}
public class Test {

}
